(a) Field of the Invention
The present invention relates to an apparatus and method of classifying packets, and more particularly, to an apparatus and method of classifying packets that can support quality of service (QoS) in a network system.
The present invention was supported by the IT R&D program of MIC/IITA [2006-S-009-02, The Development of WiBro Service and Operating Standard].
(b) Description of the Related Art
With good QoS, important packets are prevented from being lost, unnecessary packets are reduced, and immediate processing of packets that need the same is performed, thereby providing a high quality service to a user. In order to provide the QoS, a process of analyzing characteristics of packets and classifying the packets needs to be firstly performed.
Packets are classified using data that is obtained by analyzing the packets and specific field data that is included in headers of various packets in layers ranging from a layer 2 to a layer 4.
Examples of representative specific fields that are used to classify packets include a destination MAC address, a source MAC address, a virtual local area network (VLAN) ID, a VLAN user priority, an Ethernet type, an IP precedence, a differentiated service code point (DSCP), an Internet protocol (IP) type, a source IP address, a destination IP address, a layer-4 source port, and a layer-4 destination port.
When the packets are classified, only one of the above-described fields, combinations of some fields, or combinations of all fields may be used. In recent years, as various types of QoS have been required, the number and types of the fields that are used when classifying the packets have been gradually increased.
The packet classification includes a process of determining whether predetermined key data, which is composed of data corresponding to the fields obtained by analyzing the packets, satisfies a predetermined condition. A is packet classification rule is compared with the key data that is composed of data corresponding to the fields. The packet classification determines which of pluralities of packet classification rules including the key data is most preferable and derives a reasonable result.
A field search is needed to classify packets. Examples of a method of searching fields include a prefix match search, a range match search, and an exact match search.
The destination MAC address, the source MAC address, the source IP address, and the destination IP address generally indicate addresses at points where packets are generated and addresses at points that the packets reach, and are used together with a netmask. The netmask is used to locally or logically separate a network. In order to prevent non-authenticated or unnecessary packets from being circulated in a strictly managed network in terms of QoS, packets that are generated at authenticated addresses are allowed, packets that are generated at specific addresses are interrupted, and packets that are generated at addresses in a non-allowable range using a netmask are interrupted. In the case of using the netmask, only a maximum value in an allowable range is generally designated. In consideration of this point, a masking method is used to process data, such as a MAC address or an IP address. That is, when address data extracted from the packets is converted into bits, some bits are masked and the other bits are inspected to determine whether the address data has a desired value or type. Further, the prefix match search uses the above-described process to determine whether items that satisfy a predetermined condition exist in a predetermined search table.
In the cases of the layer-4 source port and the layer-4 destination port, some communication protocols may use specific port numbers and other communication protocols may use arbitrary port numbers within a predetermined range. In consideration of this case, a process of determining whether data extracted from packets is within a predetermined range and items that satisfy the predetermined condition exist in a predetermined search table is a range match search.
The virtual LAN identifier, the Ethernet type, and the IP type are defined to use specific values with respect to a specific network or specific communication protocol. In consideration of this case, a process of determining whether data extracted from packets has a specific value or type is performed to determine whether items that satisfy the predetermined condition exist in a predetermined search table, which is called an exact match search.
At the present time, as a generally used packet classification method, there is a packet classification method that uses a ternary content addressable memory (TCAM). The TCAM provides a structure in which the prefix match search can be simultaneously performed on all items constituting the TCAM, when predetermined key data is input. In an environment where a high-speed network processor or a CPU is provided or a space occupied by the TCAM is not important, a packet classification method using the TCAM may be effective.
However, if the amounts of key data input to the TCAM and classification rules stored in the TCAM are increased, that is, kinds of the fields that include the key data and the classification rules as constituent elements are increased, a memory utilization rate of the TCAM is lowered and the number of items constituting the TCAM is excessively increased. That is, when most of field data is fixed and only specific field data is changed, if this is represented as a classification rule, a large amount of memory resources are unnecessarily used.
The TCAM is not structurally suitable for the range match search. In order to obtain a range match search effect using the TCAM, pluralities of prefix match rules need to be sacrificed. That is, pluralities of items are needed to represent a range match rule as a prefix match rule using the TCAM.
In order to alleviate the above-described drawback, in recent years, a TCAM structure that can simultaneously perform a prefix match search and a range match search has been suggested. However, if kinds of the fields included in the classification rule and the key data are increased, a memory utilization rate is lowered.
As a method suggested for the purpose of alleviating the drawback in the packet classification method using the TCAM, there is a method in which a primary search is performed on each of the fields and a secondary search is then performed on key data that includes primary search results as constituent elements.
A primary search unit may be configured to perform the prefix match search, the range match search, and the exact match search, respectively or in a partially combined way. When an item satisfying a predetermined condition with respect to a specific field exists in a predetermined search table, the primary search unit outputs a search result in a predetermined form.
The primary search result may become a bit vector that represents a searched result for all items in the predetermined search table as bits, or an identifier (ID) for a specific item that satisfies a predetermined condition. The primary search result may be differently represented depending on how a secondary search unit outputting a final packet classification result is configured. That is, the primary search result may be differently represented depending on a method of configuring key data input to the secondary search unit.
However, the method of outputting a bit vector as a search result has a drawback in that, when items of the search table increase, the amount of key data for a secondary search excessively increases, which causes many restrictions at the time of substantially implementing the method.
In addition, the method of outputting an ID for a specific item as a search result has a problem in that, when a result that is obtained by performing a prefix match search or a range match search is output, the result indicates the most preferable search result rather than the best search result. That is, when the prefix match search or the range match search is performed, pluralities of items that satisfy a predetermined condition may be generated with respect to a specific field, and the most preferable result among the search results is output. If the search table is configured such that the predetermined conditions for the individual items in the search table do not overlap each other, the search results are independent from each other. In this case, however, flexibility of a search table operation is lowered, which makes it difficult to make various packet classification rules.
The secondary search unit processes key data that includes the primary search results as constituent elements. Accordingly, the predetermined search table in the secondary search unit is composed of rule data that includes the primary search results as constituent elements.
Next, a problem that occurs when a secondary search is performed using the primary search result that corresponds to outputting an ID for the specific item is exemplified. Table 1 shows an original packet classification policy.
TABLE 1SourceDestinationItemIP AddressIP AddressResultR1123.456.7.*123.456.*.*C1R2123.456.*.*123.456.8.*C2
In this case, R1 and R2 indicate packet classification rules. In the case of R1, if a source IP address is 123.456.7.* and a destination IP address is 123.456.*.*, a packet classification result becomes C1. Here, * is associated with a method that indicates an IP address, and may have an arbitrary value in a range of 0 to 2556.
Table 2 is a primary search table that includes source IP addresses as items.
TABLE 2SourceIP AddressResult123.456.7.*X1123.456.*.*X2
In Table 2, when a source IP address of input packets is 123.456.7.*, both X1 and X2 may be a search result, but it is preferable for X1 to be the search result.
Table 3 is a primary search table that includes destination IP addresses as items.
TABLE 3DestinationIP AddressResult123.456.8.*Y1123.456.*.*Y2
In Table 3, when a destination IP address of input packets is 123.456.8.*, both Y1 and Y2 may be a search result, but it is preferable for Y1 to be the search result.
Table 4 is a packet classification rule table that uses the primary search results of Tables 2 and 3 in consideration of Table 1.
TABLE 4Result forResult for SourceDestinationIP AddressIP AddressSearch TableSearch TableResultX1Y2C1X2Y1C2
For example, when a source IP address of input packets is 123.456.7.* and a destination IP address is 123.456.8.*, it is determined on the basis of Table 1 that C1 or C2 needs to be output as the search result. However, the primary search result that is determined on the basis of Table 2 is X1 and the primary search result that is determined on the basis of Table 3 is Y1, and thus the search results shown in Tables 2 and 3 are not matched with the search results shown in Table 4, Accordingly, a packet classification policy needs to be modified as shown in Table 5 and a packet classification rule table needs to be modified as shown in Table 6.
TABLE 5SourceDestinationItemIP AddressIP AddressResultR1123.456.7.*123.456.*.*C1R2123.456.*.*123.456.8.*C2R3123.456.7.*123.456.8.*C3
TABLE 6Result forResult for SourceDestinationIP AddressIP AddressSearch TableSearch TableResultX1Y2C1X2Y1C2X1Y1C3
As described above, in order to remove ambiguity that may occur whenever an item is added to the primary search table, in consideration of all pluralities of search results that can be provided by the primary search table, related contents need to be written in the packet classification rule, which causes inconvenience. When a large number of fields are included in the packet classification rule, memory utilization efficiency is lowered due to unnecessary items.
The above information disclosed in this Background section is only for enhancement of understanding of the background of the invention and therefore it may contain information that does not form the prior art that is already known in this country to a person of ordinary skill in the art.